package leetcode.sort;

@SuppressWarnings("all")
public class MergeSort extends AbstractSort {

    int[] leftArray;

    public MergeSort(int[] array) {
        super(array);
    }

    @Override
    protected void sort() {
        leftArray = new int[array.length];
        merge(0, array.length - 1);
    }

    private void merge(int left, int right) {
        // 终止条件
        if (left >= right) return;
        // 递归划分
        int mid = (left + right) >> 1;
        merge(left, mid);
        merge(mid + 1, right);
        // 合并阶段
        int i = left, j = mid + 1;
        for (int k = left; k <= right; k++) {
            leftArray[k] = array[k];
        }
        for (int k = left; k <= right; k++) {
            if (i == mid + 1)
                array[k] = leftArray[j++];
            else if (j == right + 1 || leftArray[i] <= leftArray[j])
                array[k] = leftArray[i++];
            else {
                array[k] = leftArray[j++];
            }
        }
    }
}
